The present invention relates generally to cryptography, and more particularly, to a method and system for non-malleable and non-interactive cryptographic commitment in a network.
The widespread use of computers and computer networks has heightened the need for security. The explosive growth of, for example, the Internet, including electronic commercial transactions and funds transfer, has increased the need for security in communications, data storage and management. It has also served to demonstrate that designing secure communication protocols is a complex issue, requiring considerable expertise and research.
Although the Internet has become the most economical means for communication between two or more remote sites, it does not provide protection for transmitted information. As a result, cryptographic protocols have been developed for securing electronic communication between two or more sites.
A fundamental cryptographic protocol is a "commitment" protocol. A commitment protocol generally specifies the steps for secured communication between two probabilistic polynomial-time players (i.e., a sender and a receiver). The communication between the sender and the receiver includes a commitment phase and a de-commitment phase.
In the commitment phase, based on information a sender desires to communicate to a receiver, the sender builds and sends to the receiver a commit message, such that when the receiver receives the commit message the receiver cannot retrieve the information from the commit message. In the de-commitment phase, the sender builds and sends to the receiver a de-commit message, which enables the receiver to retrieve the information from the commit message, such that the receiver is assured that the retrieved information is the information the sender committed to in the commitment phase.
The commitment protocol is used in a wide variety of cryptographic applications, including electronic contract signing (or bidding) and multi-party computations. In an electronic contract bidding application, two or more senders, for example bidders, communicate via, for example the Internet, bids on a contract to a receiver. In such an application, each sender commits to a bid by sending a commit message to the receiver. Once the receiver receives all of the bids, each sender de-commits its respective bid by sending a de-commit message to the receiver. The receiver then determines to grant the contract to a sender that, for example, submits the lowest bid.
In an electronic contract bidding application, one problem with known commitment protocols is that the communication between a sender and a receiver is malleable. Malleable means that even if the particular commitment protocol used by each sender is computationally secure against any polynomially-bounded receiver, a sender can still potentially intercept another sender's commit message and build a related commitment message based on the intercepted commit message without determining the underlying bid in the intercepted commit message. Furthermore, the intercepting sender can also intercept the other sender's de-commit message and build a related de-commit message, such that the related de-commit message includes, for example, a lower bid than the intercepted de-commit message. Hence, the intercepting sender can underbid the other sender without explicitly determining the other sender's bid.
To address the problem of malleable commitment, D. Dolev, C. Dwork, and M. Naor, "Non-Malleable Cryptography," in Proceedings of Symposium On The Theory Of Computing (1991), discloses a non-malleable commitment protocol. The Dolev, Dwork and Naor protocol, however, is interactive, and thus inefficient, as it requires a logarithmic number of rounds of two way communication between a sender and a receiver. In addition, the protocol requires costly zero-knowledge proofs, which renders communication between the sender and receiver inefficient.
A. De Santis and G. Persiano, "Zero-Knowledge Proofs Of Knowledge Without Interaction," in the Proceedings of IEEE Foundations Of Computer Science (1996), disclose a non-interactive zero-knowledge proof of knowledge. Using the De Santis and Persiano techniques, one can implement a non-malleable commitment protocol that is non-interactive. This commitment protocol, however, can only be implemented using dense crypto-systems that are based on one or more strong algebraic assumptions. Furthermore, like the Dolev, Dwork and Naor protocol, the De Santis and Persiano commitment protocol requires costly zero-knowledge proofs.
M. Bellare and P. Rogaway, "Random Oracles Are Practical: A Paradigm For Designing Efficient Protocols," in the Proceedings of ACM Conference On Computer And Communication Security (1993), discloses a non-malleable and non-interactive commitment protocol, which uses cryptographic hash functions that behave as random oracles. The Bellare and Rogaway protocol, however, does not enable one of ordinary skill in the art to implement (or even define) such random oracles with the requisite properties for complexity-theoretic assumptions. Furthermore, because the protocol is based on heuristic assumptions, the communication between a sender and a receiver is not as secure as when using other known commitment protocols.
Therefore, it is desirable to have a method and system for overcoming the above and other disadvantages of the prior art.